{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Bottom Left Tree Value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findBottomLeftValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找树左下角的值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树的 <strong>根节点</strong> <code>root</code>，请找出该二叉树的 <strong>最底层 最左边 </strong>节点的值。</p>\n",
    "\n",
    "<p>假设二叉树中至少有一个节点。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2020/12/14/tree1.jpg\" style=\"width: 182px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>root = [2,1,3]\n",
    "<strong>输出: </strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2020/12/14/tree2.jpg\" style=\"width: 242px; \" /><strong> </strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>[1,2,3,4,null,5,6,null,null,7]\n",
    "<strong>输出: </strong>7\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉树的节点个数的范围是 <code>[1,10<sup>4</sup>]</code></li>\n",
    "\t<li><meta charset=\"UTF-8\" /><code>-2<sup>31</sup> <= Node.val <= 2<sup>31</sup> - 1</code> </li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-bottom-left-tree-value](https://leetcode.cn/problems/find-bottom-left-tree-value/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-bottom-left-tree-value](https://leetcode.cn/problems/find-bottom-left-tree-value/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,3]', '[1,2,3,4,null,5,6,null,null,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node.right:\n",
    "                q.append(node.right)\n",
    "            if node.left:\n",
    "                q.append(node.left)\n",
    "        return node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "\r\n",
    "# 最底层最左边指的不一定是左叶子\r\n",
    "class Solution:\r\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\r\n",
    "        #maxDepth = -inf(float)\r\n",
    "        maxDepth = -float('INF')\r\n",
    "        depth = 0\r\n",
    "        res = 0\r\n",
    "        def traverse(root, depth):\r\n",
    "            nonlocal maxDepth, res # 内函数里改变外函数的变量\r\n",
    "            if not root.left and not root.right:\r\n",
    "                if depth > maxDepth:\r\n",
    "                    maxDepth = depth\r\n",
    "                    res = root.val\r\n",
    "                    return res\r\n",
    "            if root.left:\r\n",
    "                depth += 1\r\n",
    "                traverse(root.left, depth)\r\n",
    "                depth -= 1\r\n",
    "            if root.right:\r\n",
    "                depth += 1\r\n",
    "                traverse(root.right, depth)\r\n",
    "                depth -= 1\r\n",
    "            \r\n",
    "        traverse(root, depth)\r\n",
    "        return res\r\n",
    "\r\n",
    "# 层序遍历\r\n",
    "from collections import deque    \r\n",
    "class Solution2:\r\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\r\n",
    "        # depth = 0\r\n",
    "        # order = 0\r\n",
    "        que = deque([root])\r\n",
    "        while que:\r\n",
    "            # depth += 1\r\n",
    "            size = len(que)\r\n",
    "            for i in range(size):\r\n",
    "                cur = que.popleft()\r\n",
    "                if cur.left:\r\n",
    "                    que.append(cur.left)\r\n",
    "                if cur.right:\r\n",
    "                    que.append(cur.right)\r\n",
    "                if i == 0: # 层序遍历到最后一层的第一个值\r\n",
    "                    res = cur.val\r\n",
    "        return res\r\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        queue = collections.deque([root])\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "        return node.val\n",
    "\n",
    "        #自写"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        import queue\n",
    "        q = queue.Queue()\n",
    "        q_next_layer = queue.Queue()\n",
    "        ans = root.val\n",
    "        q.put(root)\n",
    "        while not q.empty():\n",
    "            node = q.get()\n",
    "            if node is not None:\n",
    "                if node.left is not None:\n",
    "                    q_next_layer.put(node.left)\n",
    "                if node.right is not None:\n",
    "                    q_next_layer.put(node.right)\n",
    "            if q.empty():\n",
    "                if not q_next_layer.empty():\n",
    "                    tmp = q\n",
    "                    q = q_next_layer\n",
    "                    q_next_layer = queue.Queue()\n",
    "                    ans = q.queue[0].val\n",
    "                else:\n",
    "                    pass\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        queue = list()\n",
    "        queue.append(root)\n",
    "        while(queue):\n",
    "            for _  in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "        return node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        # 迭代法\n",
    "        if not root:\n",
    "            return 0\n",
    "        que = collections.deque()\n",
    "        que.append(root)\n",
    "        result = 0\n",
    "        while que:\n",
    "            for i in range(len(que)):\n",
    "                cur = que.popleft()\n",
    "                if i == 0:\n",
    "                    result = cur.val\n",
    "                if cur.left:\n",
    "                    que.append(cur.left)\n",
    "                if cur.right:\n",
    "                    que.append(cur.right)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        q=[]\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            cur = q.pop(0)\n",
    "            if cur.right:\n",
    "                q.append(cur.right)\n",
    "            if cur.left:\n",
    "                q.append(cur.left)\n",
    "        return cur.val\n",
    "            \n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        stack = [root]\n",
    "        \n",
    "        res = []\n",
    "        while stack:\n",
    "            res = [node.val for node in stack]\n",
    "            ll = []\n",
    "            for node in stack:\n",
    "                if node.left:\n",
    "                    ll.append(node.left)\n",
    "                if node.right:\n",
    "                    ll.append(node.right)\n",
    "            \n",
    "            stack = ll\n",
    "        \n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node.right: q.append(node.right)\n",
    "            if node.left: q.append(node.left)\n",
    "        return node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        queue = list()\n",
    "        queue.append(root)\n",
    "        while(queue):\n",
    "            left = queue[0]\n",
    "            for _  in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "        return node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        que = [root]\n",
    "        result = 0\n",
    "        while que:\n",
    "            for i in range(len(que)):\n",
    "                node = que.pop(0)\n",
    "                if i == 0:\n",
    "                    result = node.val\n",
    "                if node.left:\n",
    "                    que.append(node.left)\n",
    "                if node.right:\n",
    "                    que.append(node.right)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        queue = collections.deque([root])\n",
    "        levels = []\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            level = []\n",
    "            for i in range(length):\n",
    "                node = queue.popleft()\n",
    "                level.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            levels.append(level)\n",
    "        return levels[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        from collections import deque\n",
    "        queue = deque([root])\n",
    "        self.s = []\n",
    "        while queue:\n",
    "            h = []\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.popleft()\n",
    "                h.append(cur.val)\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "            self.s.extend(h)\n",
    "        return self.s[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        result = 0\n",
    "        while queue:\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if i == 0:\n",
    "                    result = node.val\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return root\n",
    "        queue = [root]\n",
    "        leftval = root.val\n",
    "        while queue:\n",
    "            leftval = queue[0].val\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return leftval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node.right:\n",
    "                q.append(node.right)\n",
    "            if node.left:\n",
    "                q.append(node.left)\n",
    "            ans = node.val\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        result = 0\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                node = queue.popleft()\n",
    "                if i == 0:\n",
    "                    result = node.val\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if (not root.left and not root.right):\n",
    "            return root.val\n",
    "        queue = [root]\n",
    "        num = 0\n",
    "        while queue:\n",
    "            num = queue[0].val\n",
    "            length = len(queue)\n",
    "            for i in range(length):\n",
    "                tem = queue.pop(0)\n",
    "                if tem.left:\n",
    "                    queue.append(tem.left)\n",
    "                if tem.right:\n",
    "                    queue.append(tem.right)\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            n = len(stack)\n",
    "            for i in range(n):\n",
    "                node = stack.pop(0)\n",
    "                if i == 0:\n",
    "                    res = node.val\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "        return node.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if (not root.left and not root.right):\n",
    "            return root.val\n",
    "        queue = [root]\n",
    "        num = 0\n",
    "        while queue:\n",
    "            num = queue[0].val\n",
    "            length = len(queue)\n",
    "            for i in range(length):\n",
    "                tem = queue.pop(0)\n",
    "                if tem.left:\n",
    "                    queue.append(tem.left)\n",
    "                if tem.right:\n",
    "                    queue.append(tem.right)\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        # BFS搜索\n",
    "        if not root:\n",
    "            return root.val\n",
    "        queue = [root]\n",
    "        left_val = root.val\n",
    "        while queue:\n",
    "            # print(queue) # 打印会超时\n",
    "            left_val = queue[0].val\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        \n",
    "        return left_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node.right:q.append(node.right)\n",
    "            if node.left:q.append(node.left)\n",
    "        return node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "# 层序遍历\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        que = collections.deque()\n",
    "        que.append(root)\n",
    "        while que:\n",
    "            for i in range(len(que)):\n",
    "                node = que.popleft()\n",
    "                if i == 0:\n",
    "                    res = node.val\n",
    "                if node.left:\n",
    "                    que.append(node.left)\n",
    "                if node.right:\n",
    "                    que.append(node.right)\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        from collections import deque\n",
    "        q = deque()\n",
    "        q.append((root, 0))\n",
    "        max_depth = -1\n",
    "        res = 0\n",
    "        while q:\n",
    "            node, depth = q.popleft()\n",
    "            if depth > max_depth:\n",
    "                res = node.val\n",
    "                max_depth = depth\n",
    "            if node.left:\n",
    "                q.append((node.left, depth+1))\n",
    "            if node.right:\n",
    "                q.append((node.right, depth+1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        q=[root]\n",
    "        res=[]\n",
    "        while q:\n",
    "            res.append([y.val for y in q][0])\n",
    "            l=[]\n",
    "            for x in q:\n",
    "                if x.left:\n",
    "                    l.append(x.left)\n",
    "                if x.right:\n",
    "                    l.append(x.right)\n",
    "            q=l\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        que = deque([root])\n",
    "        result = None\n",
    "        while que:\n",
    "            size = len(que)\n",
    "            for i in range(size):\n",
    "                node = que.popleft()\n",
    "                if i == 0:\n",
    "                    result = node.val\n",
    "                if node.left:\n",
    "                    que.append(node.left)\n",
    "                if node.right:\n",
    "                    que.append(node.right)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        q = collections.deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node.right:\n",
    "                q.append(node.right)\n",
    "            if node.left:\n",
    "                q.append(node.left)\n",
    "        return node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        q = collections.deque([root])\n",
    "        result = []\n",
    "\n",
    "        while q:\n",
    "            temp = []\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node:\n",
    "                    temp.append(node.val)\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "            if temp:\n",
    "                result.append(temp)\n",
    "        return result[-1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return None\n",
    "        cur = deque([root])\n",
    "        while cur:\n",
    "            node = cur.popleft()\n",
    "            if node.right:\n",
    "                cur.append(node.right)\n",
    "            if node.left:\n",
    "                cur.append(node.left)\n",
    "        return node.val\n",
    "              \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        # BFS(很基本的做法, 從左邊 -> 右邊)\n",
    "        \"\"\"\n",
    "        q = collections.deque([root])\n",
    "        result = []\n",
    "\n",
    "        while q:\n",
    "            temp = []\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node:\n",
    "                    temp.append(node.val)\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "            if temp:\n",
    "                result.append(temp)\n",
    "        return result[-1][0]\n",
    "        \"\"\"\n",
    "\n",
    "        # neetcode 的解法: 只需要一個 Queue 就好了(超強)\n",
    "        # 塞入到 queue 的時候, 先從右邊開始塞\n",
    "        # 如果 tree 沒有 left tree, 那 \"左邊\" 就是 right tree, \n",
    "        # 檢查最後一次有效的 node.val 即可\n",
    "        # 如果 tree 沒有 right tree, 那 \"左邊\" 依然是 left tree\n",
    "\n",
    "        # queue 先放右邊, 那就先 pop 右邊的 node\n",
    "        # 如果左邊沒有 node, 那右邊就是 \"左邊\"\n",
    "        q = collections.deque([root])\n",
    "        while q:\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node:\n",
    "                    result = node.val\n",
    "                    q.append(node.right)\n",
    "                    q.append(node.left)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node.right: queue.append(node.right)\n",
    "            if node.left: queue.append(node.left)\n",
    "        return node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        res = []\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            path = []\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                path.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(path)\n",
    "        return res[-1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        # BFS\n",
    "        q = collections.deque([root])\n",
    "        result = []\n",
    "\n",
    "        while q:\n",
    "            temp = []\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node:\n",
    "                    temp.append(node.val)\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "            if temp:\n",
    "                result.append(temp)\n",
    "        return result[-1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        # BFS\n",
    "        \"\"\"\n",
    "        q = collections.deque([root])\n",
    "        result = []\n",
    "\n",
    "        while q:\n",
    "            temp = []\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node:\n",
    "                    temp.append(node.val)\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "            if temp:\n",
    "                result.append(temp)\n",
    "        return result[-1][0]\n",
    "        \"\"\"\n",
    "\n",
    "        # neetcode 的解法: 只需要一個 Queue 就好了(超強)\n",
    "        # 塞入到 queue 的時候, 先從右邊開始塞\n",
    "        # 如果 tree 沒有 left tree, 那 \"左邊\" 就是 right tree, \n",
    "        # 檢查最後一次有效的 node.val 即可\n",
    "        # 如果 tree 沒有 right tree, 那 \"左邊\" 依然是 left tree\n",
    "\n",
    "        # queue 先放右邊, 那就先 pop 右邊的 node\n",
    "        # 如果左邊沒有 node, 那右邊就是 \"左邊\"\n",
    "        q = collections.deque([root])\n",
    "        while q:\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node:\n",
    "                    result = node.val\n",
    "                    q.append(node.right)\n",
    "                    q.append(node.left)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        # BFS\n",
    "        \"\"\"\n",
    "        q = collections.deque([root])\n",
    "        result = []\n",
    "\n",
    "        while q:\n",
    "            temp = []\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node:\n",
    "                    temp.append(node.val)\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "            if temp:\n",
    "                result.append(temp)\n",
    "        return result[-1][0]\n",
    "        \"\"\"\n",
    "\n",
    "        # neetcode 的解法: 只需要一個 Queue 就好了(超強)\n",
    "        # 塞入到 queue 的時候, 先從右邊開始塞\n",
    "        # 如果 tree 沒有 left tree, 那 \"左邊\" 就是 right tree, \n",
    "        # 檢查最後一次有效的 node.val 即可\n",
    "        # 如果 tree 沒有 right tree, 那 \"左邊\" 依然是 left tree\n",
    "        \n",
    "        q = collections.deque([root])\n",
    "        while q:\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node:\n",
    "                    result = node.val\n",
    "                    q.append(node.right)\n",
    "                    q.append(node.left)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        # BFS\n",
    "        \"\"\"\n",
    "        q = collections.deque([root])\n",
    "        result = []\n",
    "\n",
    "        while q:\n",
    "            temp = []\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node:\n",
    "                    temp.append(node.val)\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "            if temp:\n",
    "                result.append(temp)\n",
    "        return result[-1][0]\n",
    "        \"\"\"\n",
    "\n",
    "        q = collections.deque([root])\n",
    "        while q:\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node:\n",
    "                    result = node.val\n",
    "                    q.append(node.right)\n",
    "                    q.append(node.left)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        res = None\n",
    "        queue = collections.deque()\n",
    "        if root:\n",
    "            queue.append(root)\n",
    "        while queue:\n",
    "            level = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                level.append(node)\n",
    "            if level:\n",
    "                res = level[0]\n",
    "        return res.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return None\n",
    "        stack=[root]\n",
    "        res=0\n",
    "        while len(stack):\n",
    "            size=len(stack)\n",
    "            for i in range(size):\n",
    "                node=stack.pop(0)\n",
    "                res=node.val\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return []\n",
    "        ans = []\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            vals = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                vals.append(node.val)\n",
    "                if node.right: queue.append(node.right)\n",
    "                if node.left: queue.append(node.left)\n",
    "            ans.append(vals)\n",
    "        return ans[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        # BFS(很基本的做法, 從左邊 -> 右邊)\n",
    "        \"\"\"\n",
    "        q = collections.deque([root])\n",
    "        result = []\n",
    "\n",
    "        while q:\n",
    "            temp = []\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node:\n",
    "                    temp.append(node.val)\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "            if temp:\n",
    "                result.append(temp)\n",
    "        return result[-1][0]\n",
    "        \"\"\"\n",
    "\n",
    "        # neetcode 的解法: 只需要一個 Queue 就好了(超強)\n",
    "        # 塞入到 queue 的時候, 先從右邊開始塞\n",
    "        # 如果 tree 沒有 left tree, 那 \"左邊\" 就是 right tree, \n",
    "        # 檢查最後一次有效的 node.val 即可\n",
    "        # 如果 tree 沒有 right tree, 那 \"左邊\" 依然是 left tree\n",
    "\n",
    "        # queue 先放右邊, 那就先 pop 右邊的 node\n",
    "        # 如果左邊沒有 node, 那右邊就是 \"左邊\"\n",
    "        q = collections.deque([root])\n",
    "        result = 0\n",
    "        while q:\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node:\n",
    "                    result = node.val\n",
    "                    q.append(node.right)\n",
    "                    q.append(node.left)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return\n",
    "        queue = collections.deque([root])\n",
    "        last = []\n",
    "        while queue:\n",
    "            level = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                level.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            last = level\n",
    "        return last[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        res = []\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            val = []\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                val.append(node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            res.append(val[0])\n",
    "        return res[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        q = [root]\n",
    "\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            res = q[0].val\n",
    "            for _ in range(size):\n",
    "                cur = q.pop(0)\n",
    "                if cur.left: q.append(cur.left)\n",
    "                if cur.right: q.append(cur.right)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "#层序遍历最后一层的第一个？\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        queue = collections.deque([root])\n",
    "        l = []\n",
    "        while queue:\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if i==0:\n",
    "                    the_left = node.val\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            l.append(the_left)\n",
    "        return l[-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        queue = deque([root])\n",
    "        result = []\n",
    "        while queue:\n",
    "            temp = []\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.popleft()\n",
    "                temp.append(cur.val)\n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "            result.append(temp)\n",
    "        return result[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        q = deque([root])\n",
    "        ans = []\n",
    "        while q:\n",
    "            level = []\n",
    "            for _ in range(len(q)):\n",
    "                cur = q.popleft()\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "                level.append(cur.val)\n",
    "                \n",
    "            ans.append(level)\n",
    "            \n",
    "        return ans[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "\n",
    "        myq = collections.deque([root])\n",
    "        \n",
    "\n",
    "        res = []\n",
    "\n",
    "        if not root:\n",
    "            return res\n",
    "        \n",
    "        # myq.append(root.val)   \n",
    "        \n",
    "        while myq:\n",
    "            length = len(myq)\n",
    "            \n",
    "            temp = []\n",
    "            while length >0:\n",
    "                node = myq.popleft()\n",
    "                temp.append(node.val)\n",
    "                \n",
    "                length -=1\n",
    "             \n",
    "                if node.left:\n",
    "                    myq.append(node.left)\n",
    "                if node.right:\n",
    "\n",
    "                    myq.append(node.right)\n",
    "            res.append(temp)\n",
    "        return res\n",
    "    \n",
    "    \n",
    "    def bfs(self, root):\n",
    "        myq =deque([root])\n",
    "        res = [ ]\n",
    "        if not root:\n",
    "            return res\n",
    "        while myq:\n",
    "            length = len(myq)\n",
    "            temp = []\n",
    "            while length>0:\n",
    "                node = myq.popleft()\n",
    "                temp.append(node.val)\n",
    "                length -=1\n",
    "                if node.left:\n",
    "                    myq.append(node.left)\n",
    "                if node.right:\n",
    "                    myq.append(node.right)\n",
    "\n",
    "            \n",
    "            res.append(temp.copy())\n",
    "        return res \n",
    "        \n",
    "\n",
    "\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        res = self.bfs(root)\n",
    "       \n",
    "        # res = self.bfs(root)\n",
    "        print(res )\n",
    "\n",
    "        return res[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        fifo=collections.deque([root])\n",
    "        ans=root\n",
    "        while fifo:\n",
    "            ans=fifo[0]\n",
    "            for i in range(len(fifo)):\n",
    "                e=fifo.popleft()\n",
    "                if e.left:\n",
    "                    fifo.append(e.left)\n",
    "                if e.right:\n",
    "                    fifo.append(e.right)\n",
    "        return ans.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        nodeList = collections.deque([root])\n",
    "        levelNodeList = collections.deque([])\n",
    "        while nodeList:\n",
    "            size = len(nodeList)\n",
    "            for index in range(size):\n",
    "                cur = nodeList.popleft()\n",
    "                levelNodeList.append(cur)\n",
    "                if cur.left:\n",
    "                    nodeList.append(cur.left)\n",
    "                if cur.right:\n",
    "                    nodeList.append(cur.right)\n",
    "            if not nodeList:\n",
    "                leftNode = levelNodeList.popleft()\n",
    "                return leftNode.val\n",
    "            levelNodeList = collections.deque([])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def get_depth_value(self, node: Optional[TreeNode], depth):\n",
    "        if not node.left and not node.right:\n",
    "            if depth > self.max_dep:\n",
    "                self.max_dep = depth\n",
    "                self.max_dep_value = node.val\n",
    "            return\n",
    "\n",
    "        if node.left:\n",
    "            self.get_depth_value(node.left, depth + 1)\n",
    "        if node.right:\n",
    "            self.get_depth_value(node.right, depth + 1)\n",
    "\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.max_dep = -1\n",
    "        self.max_dep_value = 0\n",
    "        self.get_depth_value(root, 0)\n",
    "        return self.max_dep_value\n",
    "\n",
    "        # 迭代法\n",
    "        # if not root:\n",
    "        #     return 0\n",
    "        \n",
    "        # node_queue = deque()\n",
    "        # node_queue.append(root)\n",
    "        # result = 0\n",
    "        # while node_queue:\n",
    "        #     for i in range(len(node_queue)):\n",
    "        #         node = node_queue.popleft()\n",
    "        #         if i == 0:\n",
    "        #             result = node.val\n",
    "        #         if node.left:\n",
    "        #             node_queue.append(node.left)\n",
    "        #         if node.right:\n",
    "        #             node_queue.append(node.right)\n",
    "        \n",
    "        # return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        if root == None:\n",
    "            return None\n",
    "        from collections import deque\n",
    "        queue = deque([root])\n",
    "        leftmost_val = 0\n",
    "        \n",
    "        while queue:\n",
    "            # 遍历当前层\n",
    "            level_size = len(queue)\n",
    "            for i in range(level_size):\n",
    "                # 取出队头节点\n",
    "                node = queue.popleft()\n",
    "                # 记录最左边的节点值\n",
    "                if i == 0:\n",
    "                    leftmost_val = node.val\n",
    "                # 将左右子节点加入队列\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        \n",
    "        return leftmost_val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.max_depth = float(\"-inf\")\n",
    "        self.res = None\n",
    "        self.dfs(root, 0)\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self, root, depth):\n",
    "        if not root.left and not root.right:\n",
    "            if depth > self.max_depth:\n",
    "                self.max_depth = depth\n",
    "                self.res = root.val\n",
    "            return\n",
    "        \n",
    "        if root.left:\n",
    "            depth += 1\n",
    "            self.dfs(root.left, depth)\n",
    "            depth -= 1\n",
    "\n",
    "        if root.right:\n",
    "            depth += 1\n",
    "            self.dfs(root.right, depth)\n",
    "            depth -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        def func(root,level):\n",
    "            if not root:\n",
    "                return 0,0\n",
    "            elif not root.left and not root.right:\n",
    "                return root.val,level\n",
    "            else:\n",
    "                lval,llevel=func(root.left,level+1)\n",
    "                rval,rlevel=func(root.right,level+1)\n",
    "                resv=root.val\n",
    "                resl=level\n",
    "                if rlevel>llevel:\n",
    "                    resl=rlevel\n",
    "                    resv=rval\n",
    "                else:                    \n",
    "                    resl=llevel\n",
    "                    resv=lval\n",
    "                if root.left and not root.left.left and not root.left.right:\n",
    "                    if level+1>resl:\n",
    "                        return root.left.val,level+1\n",
    "                return resv,resl\n",
    "        a,b=func(root,0)\n",
    "        return a\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def traversal(self,root,depth):\n",
    "        if not root.left and not root.right:\n",
    "            if depth > self.max_depth:\n",
    "                self.max_depth = depth\n",
    "                self.result = root.val\n",
    "                return\n",
    "        if root.left:\n",
    "            self.traversal(root.left,depth+1)\n",
    "        if root.right:\n",
    "            self.traversal(root.right,depth+1)\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        # 迭代法\n",
    "        # if not root:\n",
    "        #     return 0\n",
    "        # que = collections.deque()\n",
    "        # que.append(root)\n",
    "        # result = 0\n",
    "        # while que:\n",
    "        #     for i in range(len(que)):\n",
    "        #         cur = que.popleft()\n",
    "        #         if i == 0:\n",
    "        #             result = cur.val\n",
    "        #         if cur.left:\n",
    "        #             que.append(cur.left)\n",
    "        #         if cur.right:\n",
    "        #             que.append(cur.right)\n",
    "        # return result\n",
    "\n",
    "        # 递归法\n",
    "        self.max_depth = float('-inf')\n",
    "        self.result = None\n",
    "        self.traversal(root,0)\n",
    "        return self.result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode(object):\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.init_dep = -1000\n",
    "        dep = 0\n",
    "        self.result = 0\n",
    "        self.count(root, dep)\n",
    "        return self.result\n",
    "\n",
    "    def count(self, root, dep):\n",
    "        if not root.left and not root.right:\n",
    "            if dep > self.init_dep:\n",
    "                self.result = root.val\n",
    "                self.init_dep = dep\n",
    "\n",
    "        if root.left:\n",
    "            dep += 1\n",
    "            self.count(root.left, dep)\n",
    "            dep -= 1\n",
    "        \n",
    "        if root.right:\n",
    "            dep += 1\n",
    "            self.count(root.right, dep)\n",
    "            dep -= 1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return None\n",
    "        self.result = None\n",
    "        self.max_depth = 0\n",
    "        self.find_last_left(root, 1)\n",
    "        return self.result\n",
    "\n",
    "    def find_last_left(self, root, depth):\n",
    "        if root.left is None and root.right is None:\n",
    "            if self.max_depth < depth:\n",
    "                self.result = root.val\n",
    "                self.max_depth = depth\n",
    "            return\n",
    "        if root.left:\n",
    "            self.find_last_left(root.left, depth+1)\n",
    "        if root.right:\n",
    "            self.find_last_left(root.right, depth+1)\n",
    "\n",
    "        \n",
    "    \n",
    "    # def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "    #     if root is None:\n",
    "    #         return None\n",
    "\n",
    "    #     last_left = None\n",
    "    #     cur_depth = None\n",
    "    #     from collections import deque\n",
    "    #     queue = deque([(root, 1)])\n",
    "    #     while len(queue) > 0:\n",
    "    #         node, depth = queue.popleft()\n",
    "    #         if depth != cur_depth:\n",
    "    #             last_left = node.val\n",
    "    #             cur_depth = depth\n",
    "    #         if node.left:\n",
    "    #             queue.append((node.left, depth+1))\n",
    "    #         if node.right:\n",
    "    #             queue.append((node.right, depth+1))\n",
    "    #     return last_left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.result = None\n",
    "        self.max_depth =  -float(\"inf\")\n",
    "        self.dfs(root,0)\n",
    "        return self.result\n",
    "    def dfs(self,node,depth):\n",
    "        if not node.right and not node.left:\n",
    "            if depth > self.max_depth:\n",
    "                self.max_depth = depth\n",
    "                self.result = node.val\n",
    "            return \n",
    "        if node.left:\n",
    "            depth = depth +1\n",
    "            self.dfs(node.left,depth)\n",
    "            depth = depth -1\n",
    "        if node.right: \n",
    "            depth = depth + 1\n",
    "            self.dfs(node.right,depth)\n",
    "            depth = depth - 1\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.MaxDepth = -1\n",
    "        self.val = -1\n",
    "        self.backtracking(root, 1)\n",
    "        return self.val\n",
    "    def backtracking(self, root, depth):\n",
    "        if not root.left and not root.right:\n",
    "            if depth > self.MaxDepth:\n",
    "                self.MaxDepth = depth \n",
    "                self.val = root.val \n",
    "        if root.left:\n",
    "                self.backtracking(root.left, depth+1)\n",
    "        if root.right:\n",
    "                self.backtracking(root.right, depth+1)\n",
    "                    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def traversal(self,root,depth):\n",
    "        if not root.left and not root.right:\n",
    "            if depth > self.max_depth:\n",
    "                self.max_depth = depth\n",
    "                self.result = root.val\n",
    "                return\n",
    "        if root.left:\n",
    "            depth += 1\n",
    "            self.traversal(root.left,depth)\n",
    "            depth -= 1\n",
    "        if root.right:\n",
    "            depth += 1\n",
    "            self.traversal(root.right,depth)\n",
    "            depth -= 1\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        # 迭代法\n",
    "        # if not root:\n",
    "        #     return 0\n",
    "        # que = collections.deque()\n",
    "        # que.append(root)\n",
    "        # result = 0\n",
    "        # while que:\n",
    "        #     for i in range(len(que)):\n",
    "        #         cur = que.popleft()\n",
    "        #         if i == 0:\n",
    "        #             result = cur.val\n",
    "        #         if cur.left:\n",
    "        #             que.append(cur.left)\n",
    "        #         if cur.right:\n",
    "        #             que.append(cur.right)\n",
    "        # return result\n",
    "\n",
    "        # 递归法\n",
    "        self.max_depth = float('-inf')\n",
    "        self.result = None\n",
    "        self.traversal(root,0)\n",
    "        return self.result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.MaxDepth = -1\n",
    "        self.val = -1\n",
    "        self.backtracking(root, 1)\n",
    "        return self.val\n",
    "    def backtracking(self, root, depth):\n",
    "        if not root.left and not root.right:\n",
    "            if depth > self.MaxDepth:\n",
    "                self.MaxDepth = depth \n",
    "                self.val = root.val \n",
    "            return \n",
    "        if root.left:\n",
    "                self.backtracking(root.left, depth+1)\n",
    "        if root.right:\n",
    "                self.backtracking(root.right, depth+1)\n",
    "                    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "\n",
    "        def trave(root):\n",
    "            if not root:\n",
    "                return 0, 0 # val, depth\n",
    "\n",
    "            left, right = trave(root.left), trave(root.right)\n",
    "\n",
    "            if left[1] == 0 and right[1] == 0:\n",
    "                return root.val, 1\n",
    "\n",
    "            if left[1] >= right[1]:\n",
    "                return left[0], left[1] + 1\n",
    "            else:\n",
    "                return right[0], right[1] + 1\n",
    "\n",
    "        return trave(root)[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return None\n",
    "        self.result = None\n",
    "        self.max_depth = 0\n",
    "        self.find_last_left(root, 1)\n",
    "        return self.result\n",
    "    # 递归遍历\n",
    "    def find_last_left(self, root, depth):\n",
    "        if root.left is None and root.right is None:\n",
    "            if self.max_depth < depth:\n",
    "                self.result = root.val\n",
    "                self.max_depth = depth\n",
    "            return\n",
    "        if root.left:\n",
    "            self.find_last_left(root.left, depth+1)\n",
    "        if root.right:\n",
    "            self.find_last_left(root.right, depth+1)\n",
    "\n",
    "        \n",
    "    # 层序遍历\n",
    "    # def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "    #     if root is None:\n",
    "    #         return None\n",
    "\n",
    "    #     last_left = None\n",
    "    #     cur_depth = None\n",
    "    #     from collections import deque\n",
    "    #     queue = deque([(root, 1)])\n",
    "    #     while len(queue) > 0:\n",
    "    #         node, depth = queue.popleft()\n",
    "    #         if depth != cur_depth:\n",
    "    #             last_left = node.val\n",
    "    #             cur_depth = depth\n",
    "    #         if node.left:\n",
    "    #             queue.append((node.left, depth+1))\n",
    "    #         if node.right:\n",
    "    #             queue.append((node.right, depth+1))\n",
    "    #     return last_left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def digui(p,cengshu):\n",
    "            if not p.left and not p.right:\n",
    "                return p.val,cengshu\n",
    "            leftval,leftmadep,rightval,rightdep = -1,cengshu,-1,cengshu\n",
    "            if p.left:\n",
    "                leftval,leftmadep = digui(p.left,cengshu+1)\n",
    "            if p.right:\n",
    "                rightval,rightdep = digui(p.right,cengshu+1)\n",
    "            if rightdep>leftmadep:\n",
    "                return rightval, rightdep\n",
    "            else:\n",
    "                return leftval,leftmadep\n",
    "        val,_ = digui(root,0)\n",
    "        return val\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.maxvalue = float(\"-inf\")\n",
    "        self.result = None\n",
    "        self.traversal(root, 0)\n",
    "        return self.result\n",
    "    \n",
    "    def traversal(self, node, depth):\n",
    "        if not node.left and not node.right:\n",
    "            if depth > self.maxvalue:\n",
    "                self.maxvalue = depth\n",
    "                self.result = node.val\n",
    "            return\n",
    "        if node.left:\n",
    "            depth += 1\n",
    "            self.traversal(node.left, depth)\n",
    "            depth -= 1\n",
    "        if node.right:\n",
    "            depth += 1\n",
    "            self.traversal(node.right, depth)\n",
    "            depth -= 1\n",
    "        \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        self.max_depth = float('-inf')\n",
    "        self.result = None\n",
    "        self.traversal(root, 0)\n",
    "        return self.result\n",
    "    \n",
    "    def traversal(self, node, depth):\n",
    "        if not node.left and not node.right:\n",
    "            if depth > self.max_depth:\n",
    "                self.max_depth = depth\n",
    "                self.result = node.val\n",
    "            return\n",
    "        \n",
    "        if node.left:\n",
    "            depth += 1\n",
    "            self.traversal(node.left, depth)\n",
    "            depth -= 1\n",
    "        if node.right:\n",
    "            depth += 1\n",
    "            self.traversal(node.right, depth)\n",
    "            depth -= 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def travel(self,node,depth):\n",
    "        if node.left == None and node.right == None:\n",
    "            if depth > self.max_depth:\n",
    "                self.max_depth = depth\n",
    "                self.num = node.val\n",
    "        if node.left:\n",
    "            depth += 1\n",
    "            self.travel(node.left,depth)\n",
    "            depth -= 1\n",
    "        if node.right:\n",
    "            depth += 1\n",
    "            self.travel(node.right,depth)\n",
    "            depth -= 1\n",
    "        return 0\n",
    "\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.num = 0\n",
    "        self.max_depth = -1\n",
    "        aa = self.travel(root,0)\n",
    "        return self.num \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "递归--超烂\n",
    "\"\"\"\n",
    "# class Solution:\n",
    "#     def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "#         self.max_depth = -1\n",
    "#         self.res = None\n",
    "#         self.traversal(root, 0)\n",
    "#         return self.res\n",
    "\n",
    "\n",
    "#     def traversal(self, cur, depth):\n",
    "#         if not cur.left and not cur.right:\n",
    "#             if depth > self.max_depth:\n",
    "#                 self.max_depth = depth\n",
    "#                 self.res = cur.val\n",
    "#             return\n",
    "\n",
    "#         if cur.left:\n",
    "#             depth += 1\n",
    "#             self.traversal(cur.left, depth)\n",
    "#             depth -= 1\n",
    "#         if cur.right:\n",
    "#             depth += 1\n",
    "#             self.traversal(cur.right, depth)\n",
    "#             depth -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.max_depth = float('-inf')\n",
    "        self.res = None\n",
    "        self.traversal(root, 0)\n",
    "        return self.res\n",
    "\n",
    "\n",
    "    def traversal(self, cur, depth):\n",
    "        if not cur.left and not cur.right:\n",
    "            if depth > self.max_depth:\n",
    "                self.max_depth = depth\n",
    "                self.res = cur.val\n",
    "            return\n",
    "\n",
    "        if cur.left:\n",
    "            depth += 1\n",
    "            self.traversal(cur.left, depth)\n",
    "            depth -= 1\n",
    "        if cur.right:\n",
    "            depth += 1\n",
    "            self.traversal(cur.right, depth)\n",
    "            depth -= 1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    res = 0\n",
    "    depth = 0\n",
    "\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.find(root, 1)\n",
    "        return self.res\n",
    "\n",
    "    def find(self, root, depth):\n",
    "        if not root:\n",
    "            return\n",
    "        if depth > self.depth:\n",
    "            self.res = root.val\n",
    "            self.depth = depth\n",
    "        self.find(root.left, depth + 1)\n",
    "        self.find(root.right, depth + 1)\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        self.max_depth = float('-inf')\n",
    "        self.result = None\n",
    "        self.traversal(root, 0)\n",
    "        return self.result\n",
    "    \n",
    "    def traversal(self, node, depth):\n",
    "        if not node.left and not node.right:\n",
    "            if depth > self.max_depth:\n",
    "                self.max_depth = depth\n",
    "                self.result = node.val\n",
    "            return\n",
    "        \n",
    "        if node.left:\n",
    "            depth += 1\n",
    "            self.traversal(node.left, depth)\n",
    "            depth -= 1\n",
    "        if node.right:\n",
    "            depth += 1\n",
    "            self.traversal(node.right, depth)\n",
    "            depth -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.maxHeight = -1\n",
    "        self.res = root.val \n",
    "\n",
    "        self.traverse(root, 0)\n",
    "        \n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root, height):\n",
    "        if root is None:\n",
    "            return \n",
    "\n",
    "        if height > self.maxHeight:\n",
    "            self.maxHeight = height\n",
    "            self.res = root.val \n",
    "        \n",
    "        self.traverse(root.left, height + 1)\n",
    "        self.traverse(root.right, height + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        max_depth = -1\n",
    "        left_num = -1\n",
    "        def dfs(root, depth):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left, depth+1)\n",
    "            dfs(root.right, depth+1)\n",
    "            nonlocal max_depth,left_num\n",
    "            if depth>max_depth:\n",
    "                max_depth = depth\n",
    "                left_num = root.val\n",
    "            \n",
    "            \n",
    "        dfs(root, 0)\n",
    "        return left_num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        maxDepth = float('-inf')\n",
    "        res = 0\n",
    "\n",
    "        def backtracking(node, depth):\n",
    "            # 终止条件\n",
    "            if not node:\n",
    "                return 0\n",
    "            # 单层递归\n",
    "            nonlocal maxDepth\n",
    "            nonlocal res\n",
    "            if depth > maxDepth:\n",
    "                maxDepth = depth\n",
    "                res = node.val\n",
    "            backtracking(node.left, depth + 1)\n",
    "            backtracking(node.right, depth + 1)\n",
    "        backtracking(root, 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.max_depth=float('-inf')\n",
    "        self.res=None\n",
    "        self.traval(root,0)\n",
    "        return self.res\n",
    "    \n",
    "    def traval(self,root,depth):\n",
    "        if depth>self.max_depth:\n",
    "            self.max_depth=depth\n",
    "            self.res=root.val\n",
    "        \n",
    "        if root.left:\n",
    "            depth+=1\n",
    "            self.traval(root.left,depth)\n",
    "            depth-=1\n",
    "        \n",
    "        if root.right:\n",
    "            depth+=1\n",
    "            self.traval(root.right,depth)\n",
    "            depth-=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.max_depth=float('-inf')\n",
    "        self.res=None\n",
    "        self.traval(root,0)\n",
    "        return self.res\n",
    "    \n",
    "    def traval(self,root,depth):\n",
    "        if not root.left and not root.right:\n",
    "            if depth>self.max_depth:\n",
    "                self.max_depth=depth\n",
    "                self.res=root.val\n",
    "        \n",
    "        if root.left:\n",
    "            depth+=1\n",
    "            self.traval(root.left,depth)\n",
    "            depth-=1\n",
    "        \n",
    "        if root.right:\n",
    "            depth+=1\n",
    "            self.traval(root.right,depth)\n",
    "            depth-=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        self.max_depth = -float(\"inf\")\n",
    "        self.traversal(root, 0)\n",
    "        return self.res\n",
    "    def traversal(self, root, depth):\n",
    "        if not root.left and not root.right:\n",
    "            if depth > self.max_depth:\n",
    "                self.max_depth = depth\n",
    "                self.res = root.val\n",
    "            return\n",
    "        if root.left:\n",
    "            self.traversal(root.left, depth+1)\n",
    "        if root.right:\n",
    "            self.traversal(root.right, depth+1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#最大深度的那一排的左1\n",
    "class Solution:\n",
    "    def max_depth(self,node,depth):\n",
    "        \n",
    "        if not node.left and not node.right:#是叶子节点\n",
    "            if depth>self.last_depth:#高度有实际的更新之时收获的第一个节点\n",
    "                self.last_depth = depth\n",
    "                self.the_node = node.val\n",
    "            return\n",
    "        \n",
    "        if node.left:\n",
    "            depth +=1\n",
    "            self.max_depth(node.left,depth)\n",
    "            depth -=1\n",
    "        if node.right:\n",
    "            depth +=1\n",
    "            self.max_depth(node.right,depth)\n",
    "            depth -=1\n",
    "\n",
    "\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.the_node = root.val\n",
    "        self.last_depth = 1\n",
    "        self.max_depth(root,1)\n",
    "        return self.the_node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        self.max_depth=float('-inf')\n",
    "        self.res=None\n",
    "        self.traval(root,0)\n",
    "        return self.res\n",
    "    \n",
    "    def traval(self,root,depth):\n",
    "        if root and not root.left and not root.right:\n",
    "            if depth>self.max_depth:\n",
    "                self.max_depth=depth\n",
    "                self.res=root.val\n",
    "        \n",
    "        if root.left:\n",
    "            depth+=1\n",
    "            self.traval(root.left,depth)\n",
    "            depth-=1\n",
    "        \n",
    "        if root.right:\n",
    "            depth+=1\n",
    "            self.traval(root.right,depth)\n",
    "            depth-=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        curVal = curHeight = 0\n",
    "        def dfs(node, height):\n",
    "            if node is None:\n",
    "                return\n",
    "            height += 1\n",
    "            dfs(node.left, height)\n",
    "            dfs(node.right, height)\n",
    "            nonlocal curVal, curHeight\n",
    "            if height > curHeight:\n",
    "                curHeight = height\n",
    "                curVal = node.val\n",
    "        dfs(root, 0)\n",
    "        return curVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        self.MaxDep = float('-inf')\n",
    "        cur_dep = 0\n",
    "        self.result = 0\n",
    "\n",
    "        self.MyTree(root, cur_dep)\n",
    "        return self.result\n",
    "\n",
    "    \n",
    "    def MyTree(self, root, cur_dep):\n",
    "\n",
    "        if root is None:\n",
    "            return \n",
    "\n",
    "        if root.left is None and root.right is None:\n",
    "            if cur_dep > self.MaxDep:\n",
    "                self.result = root.val\n",
    "                self.MaxDep = cur_dep\n",
    "                # return result\n",
    "\n",
    "        if root.left:\n",
    "            cur_dep += 1\n",
    "            self.MyTree(root.left, cur_dep)\n",
    "            cur_dep -= 1\n",
    "\n",
    "        if root.right:\n",
    "            cur_dep += 1\n",
    "            self.MyTree(root.right, cur_dep)\n",
    "            cur_dep -= 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
